package cn.corffen.test.algorithm.leetcode.easy.other;

import com.corffen.libsource.Stack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class OtherDemo {

    public int hammingWeight(int n) {
        String s = Integer.toString(n, 2);
        int len = s.length();
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }

    /**
     * 数字n 与掩码 000...1 进行与运算 可以得到末位的数字为1还是0
     * 因为是int类型的,所以从后往前每次运算都能得到其在第n-i的数字
     * 如果是1就将count+1
     *
     * @param n
     * @return
     */
    public int hammingWeight1(int n) {
        int mask = 1;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                count++;
            }
            mask = mask << 1;
        }
        return count;
    }

    /**
     * n 与 n-1 进行与运算 会将n的最低位的1 变为0.
     *
     * @param n
     * @return
     */
    public int hammingWeight2(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;
    }

    public int hammingDistance(int x, int y) {
        int mask = 1;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((x & mask) != (y & mask)) {
                count++;
            }
            mask <<= 1;
        }
        return count;
    }

    /**
     * 这题可以转换为两个整数异或运算之后,统计1的位数
     * Integer中提供了bitCount函数
     * 或者使用 hammingWeight2 这个方法也叫作 布莱恩-克尼根 算法
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance2(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

    /**
     * 颠倒给定的 32 位无符号整数的二进制位。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入: 00000010100101000001111010011100
     * 输出: 00111001011110000010100101000000
     * 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     * 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
     * 示例 2：
     * <p>
     * 输入：11111111111111111111111111111101
     * 输出：10111111111111111111111111111111
     * 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     * 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
     *
     * @param n
     * @return
     */
    public int reverseBits(int n) {
        int ret = 0;
        int pow = 31;
        while (n != 0) {
            ret += ((n & 1) << pow);
            pow--;
            n >>>= 1;
        }
        return ret;
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        if (numRows <= 0) {
            return triangle;
        }
        triangle.add(new ArrayList<Integer>());
        triangle.get(0).add(1);
        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> preRow = triangle.get(i - 1);
            row.add(1);
            for (int j = 1; j < i; j++) {
                row.add(preRow.get(j) + preRow.get(j - 1));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }

    public boolean isValid(String s) {
        char[] stack = new char[s.length() + 1];
        int top = 1;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack[top++] = c;
            } else if (c == ')' && stack[top--] != '(') {
                return false;
            } else if (c == '}' && stack[top--] != '{') {
                return false;
            } else if (c == ']' && stack[top--] != '[') {
                return false;
            }
        }
        return top == 1;
    }

    /**
     * 缺失数字
     * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,0,1]
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: [9,6,4,2,3,5,7,0,1]
     * 输出: 8
     *
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int miss = len;
        for (int i = 0; i < len; i++) {
            miss ^= (i ^ nums[i]);
        }
        return miss;
    }
}
